Once we start talking about proofs in Predicate Logic, we’ll see that there’s often a close correspondence between the structure of formulas and the structure of their proofs. It is therefore important to be able to read an English-language (mathematical) statement and understand what sort of formula it corresponds to, since that tells us how to approach a proof of that statement.
Especially when it comes to predicate logic, we can’t always rely on the sentence to have obvious keywords like “if…then…”. Similarly, quantifiers are often left implicit.
The following examples show this in action:
Example
Translation: \[ \forall S\ \forall T\ \bigl(\,S\subseteq T \longleftrightarrow \forall x\,(x\in S\ \to\ x\in T)\,\bigr) \]
- Definition: Two sets are disjoint if they have no element in common.
Translation: \[ \forall S\ \forall T\ \bigl(\,\mathrm{disjoint}(S,T) \longleftrightarrow \lnot \exists x\,(x\in S\ \land\ x\in T)\,\bigr) \] or:
\[ \forall S\ \forall T\ \bigl(\,\mathrm{disjoint}(S,T) \longleftrightarrow \forall x\,(x\not\in S\ \lor\ x\not\in T)\,\bigr) \] where \(x\not\in S\) means \(\lnot(x\in S)\).
- The union of two nonempty sets is nonempty.
Translation: \[ \forall S\ \forall T\ \bigl(\,(\exists x\ x\in S) \land (\exists y\ y \in S)\ \to\ (\exists z\ z\in S\cup T)\,\bigr) \]
Example
Definition: A function \(f\) is idempotent if \(f(x) = f(f(x))\).
Translation: \[ \forall f\ \biggl(\mathrm{idempotent}(f) \longleftrightarrow \forall x\ \bigl(\,f(x) = f(f(x))\,\bigr)\biggr) \]
Definition: \(y\) is a fixed point of \(f\) if \(f(y) = y\).
Translation: \[ \forall f\ \forall y\ \bigl(\,\mathrm{fp}(f,y) \longleftrightarrow f(y) = y\,\bigr) \]
Theorem: Every idempotent function has a range equal to its fixed points.
(Notation: \(\mathrm{Rng}(f)\) is the range of \(f\), the set of possible outputs.)
(Notation: \(\mathrm{Fix}(f)\) is the set of fixed points of \(f\).)
Translation: \[ \forall f\ \bigl(\,\mathrm{idempotent}(f) \to \mathrm{Rng}(f) = \mathrm{Fix}(f)\,\bigr) \]
Example
Set \(S\) is empty (contains no elements).
Translation: \[ \lnot \exists x\ x\in S \] or \[ \forall x\ x\not\in S \] (where \(x\not\in S\) means \(\lnot(x\in S)\).)
Set \(S\) has at least one element.
Translation: \[ \exists x\ x\in S \] i.e., there exists something that is an element in \(S\).
Set \(S\) has exactly one element.
Translation: \[ \exists x\ \bigl(x\in S \land \lnot\exists y\ (y\in S \land x\not= y)\bigr) \] (where \(x\not= y\) means \(\lnot(x = y)\)), i.e., there is one element \(x\) in \(S\) and no element in \(S\) is different from \(x\).
Or, \[ \exists x\ \bigl(x\in S \land \forall y\ (y\in S \to y=x)\bigr) \] i.e., there is an element is \(S\) such that every element in \(S\) is equal to it.
Set \(S\) has at least two elements.
Translation: \[ \exists x\ \exists y\ (x\in S\land y\in S\land x\not= y) \]
Set \(S\) has exactly two elements.
Translation: \[ \exists x\ \exists y\ \bigl(x\in S \land y\in S\land x\not= y\land \forall z\ (z\in S\to z=x\lor z=y)\bigr) \] i.e., there are two elements \(x\) and \(y\) in \(S\) that are different from each other, and every element in \(S\) is either \(x\) or \(y\).
Previous: 2.1 Predicate Logic